/* Simple grep.  Only supports ^ . * $ operators. */

#include "stat.h"
#include "types.h"
#include "user.h"

char buf[1024];
int match(char *, char *);

void grep(char *pattern, int fd)
{
    int n, m;
    char *p, *q;

    m = 0;
    while ((n = read(fd, buf + m, sizeof(buf) - m - 1)) > 0) {
        m += n;
        buf[m] = '\0';
        p = buf;
        while ((q = strchr(p, '\n')) != 0) {
            *q = 0;
            if (match(pattern, p)) {
                *q = '\n';
                write(1, p, q + 1 - p);
            }
            p = q + 1;
        }
        if (p == buf)
            m = 0;
        if (m > 0) {
            m -= p - buf;
            memmove(buf, p, m);
        }
    }
}

int main(int argc, char *argv[])
{
    int fd, i;
    char *pattern;

    if (argc <= 1) {
        printf(2, "usage: grep pattern [file ...]\n");
        exit();
    }
    pattern = argv[1];

    if (argc <= 2) {
        grep(pattern, 0);
        exit();
    }

    for (i = 2; i < argc; i++) {
        if ((fd = open(argv[i], 0)) < 0) {
            printf(1, "grep: cannot open %s\n", argv[i]);
            exit();
        }
        grep(pattern, fd);
        close(fd);
    }
    exit();
}

/*
 * Regexp matcher from Kernighan & Pike,
 * The Practice of Programming, Chapter 9.
 */

int matchhere(char *, char *);
int matchstar(int, char *, char *);

int match(char *re, char *text)
{
    if (re[0] == '^')
        return matchhere(re + 1, text);
    do { // must look at empty string
        if (matchhere(re, text))
            return 1;
    } while (*text++ != '\0');
    return 0;
}

/* matchhere: search for re at beginning of text */
int matchhere(char *re, char *text)
{
    if (re[0] == '\0')
        return 1;
    if (re[1] == '*')
        return matchstar(re[0], re + 2, text);
    if (re[0] == '$' && re[1] == '\0')
        return *text == '\0';
    if (*text != '\0' && (re[0] == '.' || re[0] == *text))
        return matchhere(re + 1, text + 1);
    return 0;
}

/* matchstar: search for c*re at beginning of text */
int matchstar(int c, char *re, char *text)
{
    do {
        /* a * matches zero or more instances */
        if (matchhere(re, text))
            return 1;
    } while (*text != '\0' && (*text++ == c || c == '.'));
    return 0;
}
